#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    ListNode* addInList(ListNode* head1, ListNode* head2)
    {
        stack<int> h1, h2;
        while (head1 != nullptr)
        {
            h1.push(head1->val);
            head1 = head1->next;
        }
        while (head2 != nullptr)
        {
            h2.push(head2->val);
            head2 = head2->next;
        }
        ListNode* NewHead, * cur;
        NewHead = cur = new ListNode(-1);
        cur->next = nullptr;
        int Next = 0;
        while (!h1.empty() || !h2.empty())
        {
            int value = 0;
            if (!h1.empty())
            {
                value += h1.top();
                h1.pop();
            }
            if (!h2.empty())
            {
                value += h2.top();
                h2.pop();
            }
            value += Next;
            Next = value / 10;
            value = value % 10;
            ListNode* NewNode = new ListNode(value);
            NewNode->next = cur->next;
            cur->next = NewNode;
        }
        if (Next)
        {
            ListNode* NewNode = new ListNode(Next);
            Next = 0;
            NewNode->next = cur->next;
            cur->next = NewNode;
        }
        NewHead = cur->next;
        delete cur;
        return NewHead;
    }
};

